/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/3sum-closest
   @Language: C++
   @Datetime: 19-05-29 11:03
   */

class Solution {
public:
	int threeSumClosest(vector<int>& nums, int target) {
		sort(nums.begin(),nums.end());
		long sum=INT_MAX;
		for(int i=0; i<nums.size(); ++i){
			if(i>0 && nums[i-1]==nums[i]) continue;
			for(int j=i+1, k=nums.size()-1; j<k;){
				if(j>i+1 && nums[j-1]==nums[j]){
					++j;
					continue;
				}
				if(k+1<nums.size()-1 && nums[k]==nums[k+1]){
					--k;
					continue;
				}
				const long t=nums[i]+nums[j]+nums[k];
				sum=abs(sum-target)>abs(t-target)?t:sum;
				if(t>target) --k;
				else if(t<target) ++j;
				else return sum;
			}
		}
		return sum;
	}
};
